package com.sise.Linked;

/**
 *      148. 排序链表
 *
 *      给你链表的头结点 head，请将其按 升序 排列并返回 排序后的链表 。
 *      你可以在 O(n logn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 *
 *      题解：
 *      本题采用的是 归并排序，第一个问题就是如何处理好链表的指向问题，在这里可以使用 合并两个有序链表进行解决(有序链表)，
 *      那么前提就是 两个有序链表，故此我们需要递归得到最后两个数值 val，通过不断的分割中心节点(快慢指针)即可得到.
 *
 *      1、获取中心节点(快慢指针)，分割为左右链表
 *      2、合并有序链表
 *      3、递归返回 合并好的链表
 */
public class _148_sortList {

    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode midNode = middleNode(head);                // 获取当前链表的中心节点，将其下个节点设置为 null，分割为两条链表
        ListNode rightHead = midNode.next;
        midNode.next = null;

        ListNode left = sortList(head);                     // 获取左链表的起点
        ListNode right = sortList(rightHead);               // 获取右链表的起点

        return mergeTwoLists(left, right);                  // 返回合并后的有序链表 (归并排序)，这里的合并放在最后，故此是从小合并到大
    }

    // 找到链表中间节点，使用的是快慢指针
    private ListNode middleNode(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序链表
    private ListNode mergeTwoLists(ListNode one, ListNode two) {
        ListNode sentry = new ListNode(-1);     // 设置哑结点。到时候由 sentry.next 即可获取新链表的头部
        ListNode cur = sentry;

        while (one != null && two != null) {
            if (one.val < two.val) {            // 取出两个链表中的大值 赋值给新的链表
                cur.next = one;
                one = one.next;
            } else {
                cur.next = two;
                two = two.next;
            }
            cur = cur.next;                     // 新链表的当前节点 往后移动一步
        }
        cur.next = one != null ? one : two;     // 接入最后剩余的链表
        return sentry.next;                     // 返回链表的头部
    }
}
